package Offer;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 *  字符串的排列
 * 根据字符串排列的特点，考虑深度优先搜索所有排列方案。即通过字符交换，先固定第 11 位字符（ nn 种情况）、
 * 再固定第 22 位字符（ n-1n−1 种情况）、... 、最后固定第 nn 位字符（ 11 种情况）。
 * 当字符串存在重复字符时，排列方案中也存在重复的排列方案。为排除重复方案，需在固定某位字符时，
 * 保证 “每种字符只在此位固定一次” ，即遇到重复字符时不交换，直接跳过。从 DFS 角度看，此操作称为 “剪枝” 。
 * @author 是阿秋啊
 * @date 2022/08/17 16:09
 **/
public class Num38 {
    List<String> list = new ArrayList<>();
    char[] c;
    public String[] permutation(String s) {
        c = s.toCharArray();
        dfs(0);
        return list.toArray(new String[list.size()]);
    }
    public void dfs(int x) {
        if(x == c.length - 1) {
            list.add(String.valueOf(c));
            return;
        }
        //防止同一层递归出现重复元素
        HashSet<Character> set = new HashSet<>();
        for(int i = x; i < c.length; i++){
            //剪枝
            if(set.contains(c[i])) continue;
            set.add(c[i]);
            swap(i,x);
            dfs(x + 1);
            swap(i,x);
        }
    }
    public void swap(int i, int j){
        char tmp = c[i];
        c[i] = c[j];
        c[j] = tmp;
    }
}